import java.util.*;
public class Solution37 {
    List<List<Integer>> result=new LinkedList<>();
    public void doTravel(int[] canditates,final int target,List<Integer> tmpRes,int tmpInd,int tmpSum){
        if(tmpSum>=target){
            if(tmpSum==target){
                result.add(new LinkedList<>(tmpRes));
            }
            return;
        }
        for (int i = tmpInd; i < canditates.length; i++) {
            int tmp=canditates[i];
            tmpRes.add(tmp);
            doTravel(canditates,target,tmpRes,i,tmpSum+tmp);
            tmpRes.remove(tmpRes.size()-1);
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        doTravel(candidates,target,new LinkedList<>(),0,0);
        return result;

    }

    public static void main(String[] args) {
        Solution37 s=new Solution37();
        System.out.println(s.combinationSum(new int[]{2,3,6,7},
        7));
    }
}
